Technological advances in computer hardware, software, and networking have led to increased demand for electronic information exchange. Such electronic communication can provide split-second, reliable data transfer between essentially any two locations throughout the world. Many industries and consumers are leveraging such technology to improve efficiency and decrease cost through web-based (e.g., on-line) services.
For example, modern game-play devices have developed capabilities of powerful computers as more-advanced integrated circuit technology has become incorporated into such game-play devices. Additionally, gaming has progressed to an online arena, where players can connect their gaming systems with other players via an online server, and communicate, coordinate, and interface with other remote players while playing a game.
Within such online arenas, network communication falls into either a client-server architecture (i.e., users communicate with a large, well-provisioned, dedicated server) or a peer-to-peer (P2P) architecture (i.e., users communicate with each other directly or via a peer). Peer-to-peer architectures and networking environments have grown considerably in population and use. In a peer-to-peer environment, many applications require selection of another peer in a network that can provide services via a network connection, such as serving as the central coordinator for a multiplayer game. As such, one can refer to the peer that is searching for services as a “client” and to a potential peer that can provide these services as a “host.” Additionally, in a peer-to-peer network there exist particular services, such as multiplayer game play, in which one or more “clients” connect to each other via a “host” intermediary, where both host and client are peers, rather than a dedicated, well-provisioned, centrally-located server. An individual peer can act as both a “host” and a “client” for different connections. In particular, effective selection or matchmaking of a client to a host based on network path quality (NPQ) can affect connectivity there between. Put differently, good network connectivity between a client and a matched host can enable optimal use of a peer-to-peer networking environment. NPQ can be any one or combination of attributes such as round trip time (RTT), upstream capacity, downstream capacity, one-way delays, etc.
Moreover, rapid estimation of round-trip time between machines remains critical for many distributed applications. In particular, content distribution systems need to find a best server for a content seeker. Likewise, distributed hash tables require selection of close machines for routing table entries and lookups. In multiplayer online games, players seek to cluster themselves so that players in the same session have low latency to each other. Similarly, users of Voice over Internet Protocol (VoIP) systems are highly sensitive to latency, and hence better server and peer selection can have a tremendous impact.
Two particular approaches to latency prediction are network coordinate systems (NCS) and Internet topology modeling. An NCS assigns each node a coordinate in a virtual metric space, such that the distance between two nodes' coordinates is a reasonable approximation of the round-trip time between them. Alternatively, the Internet topology modeling constructs a rough graph of the Internet so it can predict the latency between a given pair of nodes. Each of these approaches has limitations. An NCS constructs its world model purely based on distances observed between nodes and does not incorporate information about how the Internet is actually structured. The model thus winds up too loosely coupled to the reality of how the Internet works. Topology modeling, on the other hand, relies on a graph that takes effort to construct. It is thus typically incomplete (especially with respect to home machines) and it cannot rapidly evolve to reflect changes.